package competition;

import java.util.HashMap;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: competition
 * @Author: 江岸
 * @CreateTime: 2021-03-07 10:06
 * @Description:
 */
public class TwiceWeek47 {
    /**
     * 5680. 找到最近的有相同 X 或 Y 坐标的点
     * 给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。
     *
     * 请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小 的一个。如果没有有效点，请返回 -1 。
     *
     * 两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int nearestValidPoint(int x, int y, int[][] points) {
        int res = Integer.MAX_VALUE;
        int index = -1;
        for (int i=0;i<points.length;i++){
            if(x==points[i][0] || y==points[i][1]){
                int num =  Math.abs(x-points[i][0])+Math.abs(y-points[i][1]);
                if(res> num){
                    res = num;
                    index = i;
                }
            }
        }
        return index;
    }


    /** 5681. 判断一个数字是否可以表示成三的幂的和
     *
     * 给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。
     *
     * 对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
     *
     *
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/check-if-number-is-a-sum-of-powers-of-three
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public boolean checkPowersOfThree(int n) {
        if(n==1){
            return true;
        }
        while(n>0) {
            if (n % 3 == 0) {
                n = n / 3;
            } else {
                n = n - 1;
                if (n % 3 != 0) {
                    return false;
                }
            }
            if(n==1){
                return true;
            }
        }
        return false;
    }


    /**
     * 5682. 所有子字符串美丽值之和
     *
     * 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
     *
     *     比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
     *
     * 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "aabcb"
     * 输出：5
     * 解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。
     *
     * 示例 2：
     *
     * 输入：s = "aabcbaa"
     * 输出：17
     */
    public static int beautySum(String s) {
        if (s.length()<=2){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        char[] arr = s.toCharArray();
        for (int i=0;i<arr.length-2;i++){
            int max = 1;
            int[] ints = new int[26];
            int len = 0;
            for(int k=i;k<arr.length;k++){
                int temp = arr[k] - 'a';
                ints[temp] = ints[temp]+1;
                max = Math.max(max,ints[temp]);
                int min = Integer.MAX_VALUE;
                //最小值必须循环存放个数的数组求得
                for (int j=0;j<ints.length;j++){
                    if (ints[j]>0){
                        min = Math.min(min,ints[j]);
                    }
                }
                res = res + max - min;
            }
        }
        return res;
    }

}
